home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / networking / ip / ka9q / src.arc / IPROUTE.C < prev    next >
C/C++ Source or Header  |  1989-08-19  |  15KB  |  588 lines
  1. /* Lower half of IP, consisting of gateway routines
  2.  * Includes routing and options processing code
  3.  */
  4. #include "global.h"
  5. #include "mbuf.h"
  6. #include "internet.h"
  7. #include "timer.h"
  8. #include "netuser.h"
  9. #include "ip.h"
  10. #include "icmp.h"
  11. #include "iface.h"
  12. #include "trace.h"
  13.  
  14. static int16 hash_ip __ARGS((int32 addr));
  15. static struct route *rt_lookup __ARGS((int32 target));
  16.  
  17. struct route *Routes[32][NROUTE];    /* Routing table */
  18. struct route R_default;            /* Default route entry */
  19.  
  20. int32 Ip_addr;
  21. struct ip_stats Ip_stats;
  22.  
  23. /* Route an IP datagram. This is the "hopper" through which all IP datagrams,
  24.  * coming or going, must pass.
  25.  *
  26.  * "rxbroadcast" is set to indicate that the packet came in on a subnet
  27.  * broadcast. The router will kick the packet upstairs regardless of the
  28.  * IP destination address.
  29.  */
  30. int
  31. ip_route(bp,rxbroadcast)
  32. struct mbuf *bp;
  33. int rxbroadcast;    /* True if packet had link broadcast address */
  34. {
  35.     struct ip ip;            /* IP header being processed */
  36.     int16 ip_len;            /* IP header length */
  37.     int16 length;            /* Length of data portion */
  38.     int32 gateway;            /* Gateway IP address */
  39.     register struct route *rp;    /* Route table entry */
  40.     struct iface *iface;        /* Output interface, possibly forwarded */
  41.     int16 offset;            /* Offset into current fragment */
  42.     int16 mf_flag;            /* Original datagram MF flag */
  43.     int strict = 0;            /* Strict source routing flag */
  44.     char prec;            /* Extracted from tos field */
  45.     char del;
  46.     char tput;
  47.     char rel;
  48.     int16 opt_len;        /* Length of current option */
  49.     char *opt;        /* -> beginning of current option */
  50.     char *ptr;        /* -> pointer field in source route fields */
  51.     struct mbuf *tbp;
  52.  
  53.     Ip_stats.total++;
  54.     if(len_mbuf(bp) < IPLEN){
  55.         /* The packet is shorter than a legal IP header */
  56.         Ip_stats.runt++;
  57.         free_p(bp);
  58.         return -1;
  59.     }
  60.     /* Sneak a peek at the IP header's IHL field to find its length */
  61.     ip_len = (bp->data[0] & 0xf) << 2;
  62.     if(ip_len < IPLEN){
  63.         /* The IP header length field is too small */
  64.         Ip_stats.length++;
  65.         free_p(bp);
  66.         return -1;
  67.     }
  68.     if(cksum(NULLHEADER,bp,ip_len) != 0){
  69.         /* Bad IP header checksum; discard */
  70.         Ip_stats.checksum++;
  71.         free_p(bp);
  72.         return -1;
  73.     }
  74.     /* Extract IP header */
  75.     ntohip(&ip,&bp);
  76.  
  77.     if(ip.version != IPVERSION){
  78.         /* We can't handle this version of IP */
  79.         Ip_stats.version++;
  80.         free_p(bp);
  81.         return -1;
  82.     }
  83.     /* Trim data segment if necessary. */
  84.     length = ip.length - ip_len;    /* Length of data portion */
  85.     trim_mbuf(&bp,length);    
  86.                 
  87.     /* Process options, if any. Also compute length of secondary IP
  88.      * header in case fragmentation is needed later
  89.      */
  90.     strict = 0;
  91.     for(opt = ip.options; opt < &ip.options[ip.optlen];opt += opt_len){
  92.         /* Most options have a length field. If this is a EOL or NOOP,
  93.          * this (garbage) value won't be used
  94.          */
  95.         opt_len = uchar(opt[1]);
  96.  
  97.         switch(opt[0] & OPT_NUMBER){
  98.         case IP_EOL:
  99.             goto no_opt;    /* End of options list, we're done */
  100.         case IP_NOOP:
  101.             opt_len = 1;
  102.             break;        /* No operation, skip to next option */
  103.         case IP_SSROUTE:    /* Strict source route & record route */
  104.             strict = 1;    /* note fall-thru */
  105.         case IP_LSROUTE:    /* Loose source route & record route */
  106.             /* Source routes are ignored unless we're in the
  107.              * destination field
  108.              */
  109.             if(ip.dest != Ip_addr)
  110.                 break;    /* Skip to next option */
  111.             if(uchar(opt[2]) >= opt_len){
  112.                 break;    /* Route exhausted; it's for us */
  113.             }
  114.             /* Put address for next hop into destination field,
  115.              * put our address into the route field, and bump
  116.              * the pointer
  117.              */
  118.             ptr = opt + uchar(opt[2]) - 1;
  119.             ip.dest = get32(ptr);
  120.             put32(ptr,Ip_addr);
  121.             opt[2] += 4;
  122.             break;
  123.         case IP_RROUTE:    /* Record route */
  124.             if(uchar(opt[2]) >= opt_len){
  125.                 /* Route area exhausted; kick back an error */
  126.                 union icmp_args icmp_args;
  127.  
  128.                 icmp_args.pointer = IPLEN + opt - ip.options;
  129.                 icmp_output(&ip,bp,PARAM_PROB,0,&icmp_args);
  130.                 free_p(bp);
  131.                 return -1;
  132.             }
  133.             /* Add our address to the route */
  134.             ptr = opt + uchar(opt[2]) - 1;
  135.             ptr = put32(ptr,Ip_addr);
  136.             opt[2] += 4;
  137.             break;
  138.         }
  139.     }
  140. no_opt:
  141.  
  142.     /* See if it's a broadcast or addressed to us, and kick it upstairs */
  143.     if(ip.dest == Ip_addr || rxbroadcast){
  144. #ifdef    GWONLY
  145.     /* We're only a gateway, we have no host level protocols */
  146.         if(!rxbroadcast)
  147.             icmp_output(&ip,bp,DEST_UNREACH,PROT_UNREACH,(union icmp_args *)NULL);
  148.         free_p(bp);
  149. #else
  150.         ip_recv(&ip,bp,rxbroadcast);
  151. #endif
  152.         return 0;
  153.     }
  154.     /* Decrement TTL and discard if zero */
  155.     if(--ip.ttl == 0){
  156.         /* Send ICMP "Time Exceeded" message */
  157.         icmp_output(&ip,bp,TIME_EXCEED,0,NULLICMP);
  158.         free_p(bp);
  159.         return -1;
  160.     }
  161.     /* Look up target address in routing table */
  162.     if((rp = rt_lookup(ip.dest)) == NULLROUTE){
  163.         /* No route exists, return unreachable message */
  164.         icmp_output(&ip,bp,DEST_UNREACH,HOST_UNREACH,NULLICMP);
  165.         free_p(bp);
  166.         return -1;
  167.     }
  168.     rp->uses++;
  169.     /* Check for output forwarding and divert if necessary */
  170.     iface = rp->iface;
  171.     if(iface->forw != NULLIF)
  172.         iface = iface->forw;
  173.  
  174.     /* Find gateway; zero gateway in routing table means "send direct" */
  175.     if(rp->gateway == (int32)0)
  176.         gateway = ip.dest;
  177.     else
  178.         gateway = rp->gateway;
  179.  
  180.     if(strict && gateway != ip.dest){
  181.         /* Strict source routing requires a direct entry */
  182.         icmp_output(&ip,bp,DEST_UNREACH,ROUTE_FAIL,NULLICMP);
  183.         free_p(bp);
  184.         return -1;
  185.     }
  186.     prec = PREC(ip.tos);
  187.     del = ip.tos & DELAY;
  188.     tput = ip.tos & THRUPUT;
  189.     rel = ip.tos & RELIABILITY;
  190.  
  191.     if(ip.length <= iface->mtu){
  192.         /* Datagram smaller than interface MTU; put header
  193.          * back on and send normally
  194.          */
  195.         if((tbp = htonip(&ip,bp)) == NULLBUF){
  196.             free_p(bp);
  197.             return -1;
  198.         }
  199.         return (*iface->send)(tbp,iface,gateway,prec,del,tput,rel);
  200.     }
  201.     /* Fragmentation needed */
  202.     if(ip.flags.df){
  203.         /* Don't Fragment set; return ICMP message and drop */
  204.         icmp_output(&ip,bp,DEST_UNREACH,FRAG_NEEDED,NULLICMP);
  205.         free_p(bp);
  206.         return -1;
  207.     }
  208.     /* Create fragments */
  209.     offset = ip.offset;
  210.     mf_flag = ip.flags.mf;        /* Save original MF flag */
  211.     while(length != 0){        /* As long as there's data left */
  212.         int16 fragsize;        /* Size of this fragment's data */
  213.         struct mbuf *f_data;    /* Data portion of fragment */
  214.  
  215.         /* After the first fragment, should remove those
  216.          * options that aren't supposed to be copied on fragmentation
  217.          */
  218.         ip.offset = offset;
  219.         if(length + ip_len <= iface->mtu){
  220.             /* Last fragment; send all that remains */
  221.             fragsize = length;
  222.             ip.flags.mf = mf_flag;    /* Pass original MF flag */
  223.         } else {
  224.             /* More to come, so send multiple of 8 bytes */
  225.             fragsize = (iface->mtu - ip_len) & 0xfff8;
  226.             ip.flags.mf = 1;
  227.         }
  228.         ip.length = fragsize + ip_len;
  229.  
  230.         /* Duplicate the fragment */
  231.         dup_p(&f_data,bp,offset,fragsize);
  232.         if(f_data == NULLBUF){
  233.             free_p(bp);
  234.             return -1;
  235.         }
  236.         /* Put IP header back on */
  237.         if((tbp = htonip(&ip,f_data)) == NULLBUF){
  238.             free_p(f_data);
  239.             free_p(bp);
  240.             return -1;
  241.         }
  242.         /* and ship it out */
  243.         if((*iface->send)(tbp,iface,gateway,prec,del,tput,rel) == -1){
  244.             free_p(bp);
  245.             return -1;
  246.         }
  247.         offset += fragsize;
  248.         length -= fragsize;
  249.     }
  250.     free_p(bp);
  251.     return 0;
  252. }
  253.  
  254. static struct rt_cache Rt_cache;
  255.  
  256. /* Add an entry to the IP routing table. Returns 0 on success, -1 on failure */
  257. int
  258. rt_add(target,bits,gateway,iface)
  259. int32 target;        /* Target IP address prefix */
  260. unsigned int bits;    /* Size of target address prefix in bits (0-32) */
  261. int32 gateway;
  262. struct iface *iface;
  263. {
  264.     struct route *rp,**hp;
  265.     int16 i;
  266.     int32 mask;
  267.  
  268.     if(iface == NULLIF)
  269.         return -1;
  270.  
  271.     Rt_cache.target = 0;    /* Flush cache */
  272.  
  273.     /* Zero bits refers to the default route */
  274.     if(bits == 0){
  275.         rp = &R_default;
  276.     } else {
  277.         if(bits > 32)
  278.             bits = 32;
  279.  
  280.         /* Mask off don't-care bits */
  281.         mask = 0xffffffff;
  282.         for(i=31;i >= bits;i--)
  283.             mask <<= 1;
  284.  
  285.         target &= mask;
  286.         /* Search appropriate chain for existing entry */
  287.         for(rp = Routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  288.             if(rp->target == target)
  289.                 break;
  290.         }
  291.     }
  292.     if(rp == NULLROUTE){
  293.         /* The target is not already in the table, so create a new
  294.          * entry and put it in.
  295.          */
  296.         if((rp = (struct route *)malloc(sizeof(struct route))) == NULLROUTE)
  297.             return -1;    /* No space */
  298.         /* Insert at head of table */
  299.         rp->prev = NULLROUTE;
  300.         hp = &Routes[bits-1][hash_ip(target)];
  301.         rp->next = *hp;
  302.         if(rp->next != NULLROUTE)
  303.             rp->next->prev = rp;
  304.         *hp = rp;
  305.     }
  306.     rp->target = target;
  307.     rp->gateway = gateway;
  308.     rp->iface = iface;
  309.     rp->uses = 0;
  310.  
  311.     return 0;
  312. }
  313.  
  314. /* Remove an entry from the IP routing table. Returns 0 on success, -1
  315.  * if entry was not in table.
  316.  */
  317. int
  318. rt_drop(target,bits)
  319. int32 target;
  320. unsigned int bits;
  321. {
  322.     register struct route *rp;
  323.     unsigned int i;
  324.     int32 mask;
  325.  
  326.     Rt_cache.target = 0;    /* Flush the cache */
  327.  
  328.     if(bits == 0){
  329.         /* Nail the default entry */
  330.         R_default.iface = NULLIF;
  331.         return 0;
  332.     }
  333.     if(bits > 32)
  334.         bits = 32;
  335.  
  336.     /* Mask off don't-care bits */
  337.     mask = 0xffffffff;
  338.     for(i=31;i >= bits;i--)
  339.         mask <<= 1;
  340.  
  341.     target &= mask;
  342.  
  343.     /* Search appropriate chain for existing entry */
  344.     for(rp = Routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  345.         if(rp->target == target)
  346.             break;
  347.     }
  348.     if(rp == NULLROUTE)
  349.         return -1;    /* Not in table */
  350.  
  351.     if(rp->next != NULLROUTE)
  352.         rp->next->prev = rp->prev;
  353.     if(rp->prev != NULLROUTE)
  354.         rp->prev->next = rp->next;
  355.     else
  356.         Routes[bits-1][hash_ip(target)] = rp->next;
  357.  
  358.     free((char *)rp);
  359.     return 0;
  360. }
  361.  
  362. /* Compute hash function on IP address */
  363. static int16
  364. hash_ip(addr)
  365. register int32 addr;
  366. {
  367.     register unsigned int ret;
  368.  
  369.     ret = hiword(addr);
  370.     ret ^= loword(addr);
  371.     return ret % NROUTE;
  372. }
  373. #ifndef    GWONLY
  374. /* Given an IP address, return the MTU of the local interface used to
  375.  * reach that destination. This is used by TCP to avoid local fragmentation
  376.  */
  377. int16
  378. ip_mtu(addr)
  379. int32 addr;
  380. {
  381.     register struct route *rp;
  382.     struct iface *iface;
  383.  
  384.     rp = rt_lookup(addr);
  385.     if(rp == NULLROUTE || rp->iface == NULLIF)
  386.         return 0;
  387.  
  388.     iface = rp->iface;
  389.     if(iface->forw != NULLIF)
  390.         return iface->forw->mtu;
  391.     else
  392.         return iface->mtu;
  393. }
  394. #endif
  395. /* Look up target in hash table, matching the entry having the largest number
  396.  * of leading bits in common. Return default route if not found;
  397.  * if default route not set, return NULLROUTE
  398.  */
  399. static struct route *
  400. rt_lookup(target)
  401. int32 target;
  402. {
  403.     register struct route *rp;
  404.     int bits;
  405.     int32 tsave;
  406.     int32 mask;
  407.  
  408.     if(target == Rt_cache.target)
  409.         return Rt_cache.route;
  410.  
  411.     tsave = target;
  412.  
  413.     mask = ~0;    /* All ones */
  414.     for(bits = 31;bits >= 0; bits--){
  415.         target &= mask;
  416.         for(rp = Routes[bits][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  417.             if(rp->target == target){
  418.                 /* Stash in cache and return */
  419.                 Rt_cache.target = tsave;
  420.                 Rt_cache.route = rp;
  421.                 return rp;
  422.             }
  423.         }
  424.         mask <<= 1;
  425.     }
  426.     if(R_default.iface != NULLIF){
  427.         Rt_cache.target = tsave;
  428.         Rt_cache.route = &R_default;
  429.         return &R_default;
  430.     } else
  431.         return NULLROUTE;
  432. }
  433. /* Convert IP header in host format to network mbuf */
  434. struct mbuf *
  435. htonip(ip,data)
  436. struct ip *ip;
  437. struct mbuf *data;
  438. {
  439.     int16 hdr_len;
  440.     struct mbuf *bp;
  441.     register char *cp;
  442.     int16 checksum;
  443.     int16 fl_offs;
  444.  
  445.     hdr_len = IPLEN + ip->optlen;
  446.     if((bp = pushdown(data,hdr_len)) == NULLBUF){
  447.         free_p(data);
  448.         return NULLBUF;
  449.     }
  450.     cp = bp->data;
  451.     
  452.     *cp++ = (IPVERSION << 4) | (hdr_len >> 2);
  453.     *cp++ = ip->tos;
  454.     cp = put16(cp,ip->length);
  455.     cp = put16(cp,ip->id);
  456.     fl_offs = ip->offset >> 3;
  457.     if(ip->flags.df)
  458.         fl_offs |= 0x4000;
  459.     if(ip->flags.mf)
  460.         fl_offs |= 0x2000;
  461.  
  462.     cp = put16(cp,fl_offs);
  463.     *cp++ = ip->ttl;
  464.     *cp++ = ip->protocol;
  465.     cp = put16(cp,0);    /* Clear checksum */
  466.     cp = put32(cp,ip->source);
  467.     cp = put32(cp,ip->dest);
  468.     if(ip->optlen != 0)
  469.         memcpy(cp,ip->options,ip->optlen);
  470.  
  471.     /* Compute checksum and insert into header */
  472.     checksum = cksum(NULLHEADER,bp,hdr_len);
  473.     put16(&bp->data[10],checksum);
  474.  
  475.     return bp;
  476. }
  477. /* Extract an IP header from mbuf */
  478. int
  479. ntohip(ip,bpp)
  480. struct ip *ip;
  481. struct mbuf **bpp;
  482. {
  483.     int16 ihl;
  484.     int16 fl_offs;
  485.     char ipbuf[IPLEN];
  486.  
  487.     if(pullup(bpp,ipbuf,IPLEN) != IPLEN)
  488.         return -1;
  489.  
  490.     ip->version = (ipbuf[0] >> 4) & 0xf;
  491.     ip->tos = ipbuf[1];
  492.     ip->length = get16(&ipbuf[2]);
  493.     ip->id = get16(&ipbuf[4]);
  494.     fl_offs = get16(&ipbuf[6]);
  495.     ip->offset = (fl_offs & 0x1fff) << 3;
  496.     ip->flags.mf = (fl_offs & 0x2000) ? 1 : 0;
  497.     ip->flags.df = (fl_offs & 0x4000) ? 1 : 0;
  498.     ip->ttl = ipbuf[8];
  499.     ip->protocol = ipbuf[9];
  500.     ip->source = get32(&ipbuf[12]);
  501.     ip->dest = get32(&ipbuf[16]);
  502.  
  503.     ihl = (ipbuf[0] & 0xf) << 2;
  504.     if(ihl < IPLEN){
  505.         /* Bogus packet; header is too short */
  506.         return -1;
  507.     }
  508.     ip->optlen = ihl - IPLEN;
  509.     if(ip->optlen != 0)
  510.         pullup(bpp,ip->options,ip->optlen);
  511.  
  512.     return ip->optlen + IPLEN;
  513. }
  514. /* Perform end-around-carry adjustment */
  515. int16
  516. eac(sum)
  517. register int32 sum;    /* Carries in high order 16 bits */
  518. {
  519.     register int16 csum;
  520.  
  521.     while((csum = sum >> 16) != 0)
  522.         sum = csum + (sum & 0xffffL);
  523.     return (int16) (sum & 0xffffl);    /* Chops to 16 bits */
  524. }
  525. /* Checksum a mbuf chain, with optional pseudo-header */
  526. int16
  527. cksum(ph,m,len)
  528. struct pseudo_header *ph;
  529. register struct mbuf *m;
  530. int16 len;
  531. {
  532.     register unsigned int cnt, total;
  533.     register int32 sum, csum;
  534.     register char *up;
  535.     int16 csum1;
  536.     int swap = 0;
  537.  
  538.     sum = 0l;
  539.  
  540.     /* Sum pseudo-header, if present */
  541.     if(ph != NULLHEADER){
  542.         sum = hiword(ph->source);
  543.         sum += loword(ph->source);
  544.         sum += hiword(ph->dest);
  545.         sum += loword(ph->dest);
  546.         sum += uchar(ph->protocol);
  547.         sum += ph->length;
  548.     }
  549.     /* Now do each mbuf on the chain */
  550.     for(total = 0; m != NULLBUF && total < len; m = m->next) {
  551.         cnt = min(m->cnt, len - total);
  552.         up = (char *)m->data;
  553.         csum = 0;
  554.  
  555.         if(((long)up) & 1){
  556.             /* Handle odd leading byte */
  557.             if(swap)
  558.                 csum = uchar(*up++);
  559.             else
  560.                 csum = (int16)(uchar(*up++) << 8);
  561.             cnt--;
  562.             swap = !swap;
  563.         }
  564.         if(cnt > 1){
  565.             /* Have the primitive checksumming routine do most of
  566.              * the work. At this point, up is guaranteed to be on
  567.              * a short boundary
  568.              */
  569.             csum1 = lcsum((unsigned short *)up, cnt >> 1);
  570.             if(swap)
  571.                 csum1 = (csum1 << 8) | (csum1 >> 8);
  572.             csum += csum1;
  573.         }
  574.         /* Handle odd trailing byte */
  575.         if(cnt & 1){
  576.             if(swap)
  577.                 csum += uchar(up[--cnt]);
  578.             else
  579.                 csum += (int16)(uchar(up[--cnt]) << 8);
  580.             swap = !swap;
  581.         }
  582.         sum += csum;
  583.         total += m->cnt;
  584.     }
  585.     /* Do final end-around carry, complement and return */
  586.     return ~eac(sum) & 0xffff;
  587. }
  588.